

//LC 16 三数之和  https://leetcode-cn.com/problems/3sum/

/**
 * @param {number[]} nums
 * @return {number[][]}
 * 思路：
 * 1.排序
 *    时间复杂度O(n^2)
 *    空间复杂度O(1)
 * 2.双指针
 *   时间复杂度O(n^2)
 *   空间复杂度O(1)
 * 3.双指针+hash表
 *  时间复杂度O(n^2)
 *  空间复杂度O(n)
 *  注意：hash表的key值不能重复
 */

var threeSum = function(nums) {
  let res = [];
  nums.sort((a, b) => a - b);//结果是按照升序排列的
  console.log(nums);
  for (let i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] === nums[i - 1])//如果当前数和前一个数相同，则跳过
      continue; // 去重
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      let sum = nums[i] + nums[left] + nums[right]; // 当前数和左右两个数的和  如果等于0，则添加到结果中
      if (sum === 0) {  // 如果和为0，则添加到结果中
        res.push([nums[i], nums[left], nums[right]]);//添加到结果中
        while (left < right && nums[left] === nums[left + 1]) // 如果左边的数和左边的数相同，则跳过
          left++; // 去重
        while (left < right && nums[right] === nums[right - 1]) // 如果右边的数和右边的数相同，则跳过
          right--;  // 去重
        left++;
        right--;
      } else if (sum < 0) { // 如果和小于0，则左边的数右移
        left++;
      } else {  // 如果和大于0，则右边的数左移
        right--;
      }
    }
  }
  return res;
};
nums = [-1, 0, 1, 2, -1, -4];
console.log(threeSum(nums));